#include <cstdio>

int graph[101][101];

int main(int argc, char const *argv[]) {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        if (n == 0 && m == 0)
            break;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                graph[i][j] = -1;
            }
            graph[i][i] = 0;
        }
        for (int i = 0; i < m; ++i) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            graph[a][b] = graph[b][a] = c;
        }
        for (int k = 1; k <= n; ++k) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    if (graph[i][k] == -1 || graph[k][j] == -1)
                        continue;
                    if (graph[i][j] == -1 || graph[i][k] + graph[k][j] < graph[i][j])
                        graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
        printf("%d\n", graph[1][n]);
    }
    return 0;
}